import functools


class Solution(object):
    def minimalSteps(self, maze):
        m = len(maze)
        n = len(maze[0])
        bianhao = [[-1 for _ in range(n)] for _ in range(m)]
        op = []
        st = []
        for i in range(m):
            for j in range(n):
                if maze[i][j] == 'M':
                    bianhao[i][j] = len(op)
                    op.append((i, j))
                if maze[i][j] == 'O':
                    bianhao[i][j] = len(st)
                    st.append((i, j))
                if maze[i][j] == 'S':
                    start = (i, j)
                if maze[i][j] == 'T':
                    end = (i, j)
        n_st = len(st)
        n_op = len(op)
        s_st = [-1] * len(st)
        dist = [[-1 for _ in range(n)] for _ in range(m)]
        dist[start[0]][start[1]] = 0
        now = [start]
        d = 0
        dist_start_end = -1
        while now:
            d += 1
            next_st = []
            for x, y in now:
                for ux, uy in [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]:
                    if 0 <= ux < m and 0 <= uy < n and dist[ux][uy] == -1 and maze[ux][uy] != '#':
                        dist[ux][uy] = d
                        next_st.append((ux, uy))
                        if maze[ux][uy] == 'O':
                            s_st[bianhao[ux][uy]] = d
                        if maze[ux][uy] == 'T':
                            dist_start_end = d
            now = next_st
        if op:
            dist_op_st = [[-1 for _ in range(n_st)] for _ in range(n_op)]
            dist_op_end = [-1 for _ in range(n_op)]
            dist_start_op = [-1 for _ in range(n_op)]

            def find_dist_op_st(i):
                now = [op[i]]
                dist = [[-1 for _ in range(n)] for _ in range(m)]
                dist[now[0][0]][now[0][1]] = 0
                d = 0
                while now:
                    d += 1
                    next_st = []
                    for x, y in now:
                        for ux, uy in [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]:
                            if 0 <= ux < m and 0 <= uy < n and dist[ux][uy] == -1 and maze[ux][uy] != '#':
                                dist[ux][uy] = d
                                next_st.append((ux, uy))
                                if maze[ux][uy] == 'O':
                                    dist_op_st[i][bianhao[ux][uy]] = d
                                if maze[ux][uy] == 'T':
                                    dist_op_end[i] = d
                    now = next_st

            for i in range(n_op):
                find_dist_op_st(i)
            dist_op_op = [[-1 for _ in range(n_op)] for _ in range(n_op)]
            for i in range(n_op):
                for j in range(n_op):
                    if i == j:
                        dist_op_op[i][j] = 0
                    if i > j:
                        dist_op_op[i][j] = dist_op_op[j][i]
                    if i < j:
                        d = float('inf')
                        for q in range(n_st):
                            if dist_op_st[i][q] != -1 and dist_op_st[j][q] != -1:
                                d = min(d, dist_op_st[i][q] + dist_op_st[j][q])
                        dist_op_op[i][j] = d
                        if d == float('inf'):
                            return -1
            for i in range(n_op):
                d = float('inf')
                for j in range(n_st):
                    if s_st[j] != -1 and dist_op_st[i][j] != -1:
                        d = min(d, s_st[j] + dist_op_st[i][j])
                dist_start_op[i] = d
                if d == float('inf'):
                    return -1
            for i in range(n_op):
                if dist_op_end[i] == -1:
                    return -1

            min_dist = float('inf')

            @functools.cache
            def dfs(val, i):
                if val == 0:
                    return dist_start_op[i]
                else:
                    d = float('inf')
                    for j in range(n_op):
                        if (val >> j) & 1:
                            next_val = val ^ (1 << j)
                            d = min(d, dfs(next_val, j) + dist_op_op[j][i])
                    return d
            for i in range(n_op):
                min_dist = min(min_dist, dfs(2 ** n_op - 1, i) + dist_op_end[i])
            return min_dist
        else:
            return dist_start_end


data = Solution()
# maze = ["S#O", "M..", "M.T"]
# print(data.minimalSteps(maze))
# maze = ["S#O", "M.#", "M.T"]
# print(data.minimalSteps(maze))
# maze = ["S#O", "M.T", "M.."]
# print(data.minimalSteps(maze))
maze = ["T#O", ".##", "O..", ".#.", "OSM", "#.."]
print(data.minimalSteps(maze))
